package Alibaba;

import java.awt.geom.Ellipse2D;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2022-01-19 9:55
 *
 * 15. 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * 遍历每个元素，找到他的两数之和为0-i的二元组，然后在每个二元组上加上当前i
 */
public class threeSum15 {

    //nums为已经排序后的数组，找出数组中两数之和为target的元组
    public List<List<Integer>> twoSum(int[] nums,int start,int target){
        int left=start,right=nums.length-1;
        List<List<Integer>> res=new LinkedList<>();
        while (left<right){
            int sum=nums[left]+nums[right];
            int l=nums[left],r=nums[right];
            if (sum==target){
                List<Integer> list=new LinkedList<>();
                list.add(l);
                list.add(r);
                res.add(list);
                //跳过重复元素
                while (left<right&&nums[left]==l) left++;
                while (left<right&&nums[right]==r) right--;
            }else if (sum<target){
                while (left<right&&nums[left]==l)left++;
            }else {
                while (left<right&&nums[right]==r)right--;
            }
        }
        return res;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        int n=nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res=new LinkedList<>();
        if (n<=2) return new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //在i之后找两数之和，避免重复
            List<List<Integer>> twoSum = twoSum(nums, i+1,0 - nums[i]);
            for (int j = 0; j < twoSum.size(); j++) {
                List<Integer> list = twoSum.get(j);
                list.add(nums[i]);
                res.add(list);
            }
            while (i<n-1&&nums[i]==nums[i+1]) i++;   //跳过重复
        }
        return res;
    }

}
